package test.algorithm.dp;

/**
 * @Projectname: algorithm-training-camp
 * @Filename: LevenshteinDistance
 * @Author: FANSEA
 * @Date:2024/11/3 17:04
 */
public class LevenshteinDistance {
    public static void main(String[] args) {
        LevenshteinDistance levenshteinDistance = new LevenshteinDistance();
        System.out.println(levenshteinDistance.minDistance("horse","ros"));
    }
    public double minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        // 1.初始化dp
        int[][] dp = new int[len1+1][len2+2];
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= len2; j++) {
            dp[0][j] = j;
        }
        char[] arr1 = word1.toCharArray();
        char[] arr2 = word2.toCharArray();
        // 2.状态转移,dp[i][j]表示word1[0,i]到word2[0,j]的最小编辑距离
        for(int i=1;i<len1+1;i++){
            for (int j=1;j<len2+1;j++){
                int leftUp = dp[i-1][j-1];
                if (arr1[i-1] != arr2[j-1]){
                    leftUp++;
                }
                dp[i][j] = Math.min(Math.min(dp[i][j-1]+1,dp[i-1][j]+1),leftUp);
            }
        }
        return 1 - (double) dp[len1][len2] /Math.max(len1,len2);
    }
}
